package org.lql.algo.codecrush.hot100.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: liangqinglong
 * @date: 2025-08-30 22:19
 * @description: 77. 组合 <a href="https://leetcode.cn/problems/combinations/description/">...</a>
 **/
public class Combine {

	int n;
	int k;
	List<Integer> chosen;
	List<List<Integer>> ans;

	public List<List<Integer>> combine(int n, int k) {
		this.n = n;
		this.k = k;
		this.chosen = new ArrayList<>();
		this.ans = new ArrayList<>();
		recur(1);
		return ans;
	}

	public void recur(int pos) {
		//
		if (chosen.size() > k || chosen.size() + (n - pos + 1) < k) {
			return;
		}
		// 边界
		if (pos == n + 1) {
			ans.add(new ArrayList<>(chosen));
			return;
		}
		// 不选 pos
		recur(pos + 1);
		// 选 pos
		chosen.add(pos);
		recur(pos + 1);
		chosen.remove(chosen.size() - 1);
	}


	public static void main(String[] args) {
		Combine combine = new Combine();
		System.out.println(combine.combine(4, 2));
	}
}
